package com.wujunshen.algorithm.leetcode.dynamic.programming;

/**
 * 状态定义：dp[i][j][k] 表示在 [0, i] 区间里（状态具有前缀性质），交易进行了 j 次，并且状态为 k 时我们拥有的现金数。其中 j 和 k 的含义如下：
 * <p>
 * j = 0 表示没有交易发生；
 * j = 1 表示此时已经发生了 11 次买入股票的行为；
 * j = 2 表示此时已经发生了 22 次买入股票的行为。
 * <p>
 * 即我们 人为规定 记录一次交易产生是在 买入股票 的时候。
 * <p>
 * k = 0 表示当前不持股；
 * k = 1 表示当前持股。
 * <p>
 * 下标为 00 这一天，交易次数为 0、1、2 并且状态为 0 和 1 的初值应该如下设置：
 * <p>
 * dp[0][0][0] = 0：这是显然的；
 * dp[0][0][1]：表示一次交易都没有发生，但是持股，这是不可能的，也不会有后序的决策要用到这个状态值，可以不用管；
 * dp[0][1][0] = 0：表示发生了 1 次交易，但是不持股，这是不可能的。虽然没有意义，但是设置成 0 不会影响最优值；
 * dp[0][1][1] = -prices[0]：表示发生了一次交易，并且持股，所以我们持有的现金数就是当天股价的相反数；
 * dp[0][2][0] = 0：表示发生了 2 次交易，但是不持股，这是不可能的。虽然没有意义，但是设置成 0 不会影响最优值；
 * dp[0][2][1] = 负无穷：表示发生了 22 次交易，并且持股，这是不可能的。注意：虽然没有意义，但是不能设置成 0，这是因为交易还没有发生，必须规定当天 k 状态为 1（持股），需要参考以往的状态转移，一种很有可能的情况是没有交易是最好的情况。
 *说明：dp[0][2][1] 设置成为负无穷这件事情我可能没有说清楚。大家可以通过特殊测试用例 [1, 2, 3, 4, 5]，对比 dp[0][2][1] = 0 与 dp[0][2][1] = 负无穷 的状态转移的差异去理解。
 * <p>
 * 注意：只有在之前的状态有被赋值的时候，才可能有当前状态。
 * <p>
 * 思考输出：最后一天不持股的状态都可能成为最大利润。
 * <p>
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/8/9 14:51<br>
 */
public class 买卖股票的最佳时机III {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        // 第 2 维的 0 没有意义，1 表示交易进行了 1 次，2 表示交易进行了 2 次
        // 为了使得第 2 维的数值 1 和 2 有意义，这里将第 2 维的长度设置为 3
        int[][][] dp = new int[len][3][2];

        // 理解如下初始化
        // 第 3 维规定了必须持股，因此是 -prices[0]
        dp[0][1][1] = -prices[0];
        // 还没发生的交易，持股的时候应该初始化为负无穷
        dp[0][2][1] = Integer.MIN_VALUE;

        for (int i = 1; i < len; i++) {
            // 转移顺序先持股，再卖出
            dp[i][1][1] = Math.max(dp[i - 1][1][1], -prices[i]) ;
            dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i]);
            dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i]);
            dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i]);
        }

        return Math.max(dp[len - 1][1][0], dp[len - 1][2][0]);
    }
}
